Tutorial 5 - Using a Quantum Device to solve Weighted MIS

The Weighted Maximum Independent Set problem (WMIS) is a variant of MIS in which some nodes are given priorities.

Just as MIS, there is currently no known polynomial-time algorithm to solve WMIS for general graphs on classical (non-quantum) devices. Consequently, in practice, finding an exact solution for large graphs is generally not possible due to time and hardware limitations. For this reason, most applications of WMIS must satisfy themselves with finding approximate solutions. As it turns out, in some cases, even finding approximate solutions is considered hard. For these reasons, there is high interest in solving WMIS on Quantum Devices.

This library does just that: compile a WMIS into a form suited for execution on quantum hardware. However, by opposition to MIS, as of this writing, Quantum Devices that can execute a compiled WMIS remain experimental and generally not available outside of research laboratories.

In this tutorial, we will walk you through executing an instance of WMIS, using a quantum method on a quantum emulator.

Defining the problem

We wish to install two Python libraries called mygreatlib and anotherlib. However, there are conflicts between these Python libraries and some versions of Python, so we need to also pick the most modern version of Python that is compatible with both libraries.

In [1]:

import math
import networkx as nx

PYTHON_VERSIONS = ["Python 3.8", "Python 3.9", "Python 3.10", "Python 3.11", "Python 3.12", "Python 3.13"]

COMPATIBILITY_MY_GREAT_LIB = ["Python 3.9", "Python 3.11", "Python 3.13"]
COMPATIBILITY_ANOTHER_LIB = ["Python 3.10", "Python 3.11", "Python 3.12", "Python 3.13"]

# Define our graph.
graph = nx.Graph()
# Each node represents something we may install:
# - the libraries
graph.add_nodes_from(["mygreatlib", "anotherlib"])
# - Python
graph.add_nodes_from(PYTHON_VERSIONS)

# One may only install one version of Python at a time
for (i, version) in enumerate(PYTHON_VERSIONS):
    for other_version in PYTHON_VERSIONS[i+1:]:
        graph.add_edge(version, other_version)

# Our libraries are only compatible with some versions of Python
for version in PYTHON_VERSIONS:
    if version not in COMPATIBILITY_MY_GREAT_LIB:
        graph.add_edge("mygreatlib", version)
    if version not in COMPATIBILITY_ANOTHER_LIB:
        graph.add_edge("anotherlib", version)

# We'd like the most recent version of Python that matches all criteria,
# so let's give a higher priority to more recent versions of Python.
#
# We do this by setting attribute `weight` of the node.
for (i, version) in enumerate(PYTHON_VERSIONS):
    graph.nodes[version]["weight"] = 1 + math.log(i + 1)

# Nodes that do not have an explicit weight are impliclitly set to `1.0`.

In [2]:

from mis import MISInstance
instance = MISInstance(graph)
instance.draw()

Solving the problem

We use the same solver as in tutorial 1.

The only difference is that we pass weighting = Weighting.WEIGHTED to instruct the solver to solve the Weighted MIS problem, by opposition to the regular MIS problem.

In [3]:

from mis import BackendConfig, BackendType, SolverConfig, Weighting, MISSolver


solver_config = SolverConfig(
    # Use the QuTIP backend.
    backend = BackendConfig(
        backend = BackendType.QUTIP
    ),
    # Instruct the solver to use the weights
    weighting = Weighting.WEIGHTED,
    # Perform up to 10 quantum measures.
    max_iterations=10
)

# Run the solver
solver = MISSolver(instance, solver_config)
solutions = solver.solve()

# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
solutions[0].draw()

preprocessing - current kernel size is 8

preprocessing - complete

MIS solution: ['mygreatlib', 'anotherlib', 'Python 3.11']
Solution frequency: 1
Solution size: 3

...and that's it!

Normally, the above solution should be Python 3.13 + anotherlib + mygreatlib. Since MWIS is non-deterministic, as all quantum algorithms, there is a small chance that it could display another solution, with Python 3.11 instead of Python 3.13.

Weighted MIS may also be solved using a Greedy MIS solver, as in tutorial 2.

Difference with MIS

Formally, the difference between MIS and wMIS is that MIS maximizes the number of nodes in the solution, while wMIS maximizes the total weight of nodes in the solution, where each node has a weight of 1.0 if no weight is specified.

This means that wMIS can return a solution that is smaller (in number of nodes) than MIS.

For instance, we could de-prioritize anotherlib by giving it a weight < 0.

In [4]:

graph.nodes["anotherlib"]["weight"] = -1.0

instance = MISInstance(graph)

# Run the solver
solver = MISSolver(instance, solver_config)
solutions = solver.solve()

# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
solutions[0].draw()

preprocessing - current kernel size is 7

preprocessing - current kernel size is 1

preprocessing - complete

MIS solution: ['mygreatlib', 'Python 3.9']
Solution frequency: 1
Solution size: 2

...or we could make using Python 3.8 more important than the libraries

In [5]:

graph.nodes["anotherlib"]["weight"] = 1.0 # Restore `anotherlib` to its default priority.
graph.nodes["Python 3.8"]["weight"] = 100

instance = MISInstance(graph)

# Run the solver
solver = MISSolver(instance, solver_config)
solutions = solver.solve()

# Display results
print("MIS solution:", solutions[0].nodes)
print("Solution frequency:", solutions[0].frequency)
print("Solution size:", solutions[0].size)
solutions[0].draw()

preprocessing - current kernel size is 8

preprocessing - complete

MIS solution: ['Python 3.8']
Solution frequency: 1
Solution size: 1

Going further

If you're interested in understanding how things work behind the hood, we have written up an in-depth tutorial on how to manipulate cold atoms and laser pulses to solve this problem: https://pulser.readthedocs.io/en/stable/tutorials/mwis.html (external)